/* 1. 代码随想录 */

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

// step 1# 递归函数：判断是否存在某条路径，其和等于 count
bool traversal(struct TreeNode* cur, int count) {
    // step 2# 如果当前节点是叶子节点，判断路径和是否正好为0
    if (cur->left == NULL && cur->right == NULL && count == 0) {
        return true;
    }

    // step 3# 如果是叶子节点但路径和不为0，则返回 false
    if (cur->left == NULL && cur->right == NULL) {
        return false;
    }

    // step 4# 遍历左子树
    if (cur->left) {
        count -= cur->left->val;                      // step 4.1# 处理当前节点值
        if (traversal(cur->left, count)) return true; // step 4.2# 若找到路径直接返回
        count += cur->left->val;                      // step 4.3# 回溯
    }

    // step 5# 遍历右子树
    if (cur->right) {
        count -= cur->right->val;                       // step 5.1# 处理当前节点值
        if (traversal(cur->right, count)) return true;  // step 5.2# 若找到路径直接返回
        count += cur->right->val;                       // step 5.3# 回溯
    }

    // step 6# 所有路径都不符合
    return false;
}

// step 7# 主函数接口，初始调用
bool hasPathSum(struct TreeNode* root, int sum) {
    if (root == NULL) return false;                            // step 7.1# 空树处理
    return traversal(root, sum - root->val);                   // step 7.2# 从根节点开始，初始减去根节点值
}

/* 2. 20250415 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

/*
    功能说明：
    判断二叉树中是否存在一条从根节点到叶子节点的路径，其路径上节点值之和等于 targetSum。
*/

typedef struct TreeNode TreeNode;

bool isFind;  // 全局变量，标志是否找到满足条件的路径

// step 1# 递归查找路径和是否等于目标值
void searchSum(TreeNode *curNode, int left) {
    // step 2# 如果当前节点是叶子节点
    if (curNode->left == NULL && curNode->right == NULL) {
        // step 3# 判断当前剩余值是否为 0，是则找到路径
        if (left == 0) isFind = true;
    }

    // step 4# 递归左子树，更新剩余路径和
    if (curNode->left != NULL) 
        searchSum(curNode->left, left - curNode->left->val);

    // step 5# 递归右子树，更新剩余路径和
    if (curNode->right != NULL) 
        searchSum(curNode->right, left - curNode->right->val);

    return;
}

// step 6# 主函数入口，判断是否存在目标路径和
bool hasPathSum(struct TreeNode* root, int targetSum) {
    isFind = false;               // 初始化全局标志
    if (root == NULL) return false;  // 空树直接返回 false

    // step 7# 从根节点开始查找，减去根节点值
    searchSum(root, targetSum - root->val);

    return isFind;  // 返回最终查找结果
}
